1789D - Serval and Shift-Shift-Shift - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
char a[2][2001];
char b[2001];
int n;

void XOR(int& ac, int k)
{
    if(k>0)
    {
        for(int i=1;i<=n-k;i++)
        {
            if(a[ac][i]!=a[ac][i+k]) a[1-ac][i]='1';
            else a[1-ac][i]='0';
        }
        for(int i=n-k+1;i<=n;i++) a[1-ac][i]=a[ac][i];
    }
    else
    {
        k*=-1;
        for(int i=k+1;i<=n;i++)
        {
            if(a[ac][i]!=a[ac][i-k]) a[1-ac][i]='1';
            else a[1-ac][i]='0';
        }
        for(int i=1;i<=k;i++) a[1-ac][i]=a[ac][i];
    }

    ac=1-ac;
    return;
}

void solve()
{
    scanf("%d",&n);
    int ac=0;
    getchar();
    for(int i=1;i<=n;i++) scanf("%c",&a[0][i]);
    getchar();
    for(int i=1;i<=n;i++) scanf("%c",&b[i]);

    int ai,bi;
    ai=bi=0;
    for(int i=n;i>=1;i--)
    {
        if(a[ac][i]=='1')
        {
            ai=i;
            break;
        }
    }
    for(int i=n;i>=1;i--)
    {
        if(b[i]=='1')
        {
            bi=i;
            break;
        }
    }

    if((ai!=0 && bi==0)||(ai==0 && bi!=0))
    {
        printf("-1\n");
        return;
    }

    int cnt=0;
    vector<int> inst;
    for(int i=bi;i>=1;i--)
    {
        if(a[ac][i]==b[i]) continue;
        else
        {
            cnt++;
            inst.emplace_back(ai-i);
            XOR(ac,ai-i);
            //for(int i=1;i<=n;i++) printf("%c",a[ac][i]);
            //printf("\n");
            if(i>ai) ai=i;
        }
    }


    for(int i=1;i<=n;i++)
    {
        if(a[ac][i]=='1')
        {
            ai=i;
            break;
        }
    }
    for(int i=bi+1;i<=n;i++)
    {
        if(a[ac][i]==b[i]) continue;
        else
        {
            cnt++;
            inst.emplace_back(ai-i);
            XOR(ac,ai-i);
        }
    }

    printf("%d\n",cnt);
    for(int i=0;i<cnt;i++) printf("%d ",inst[i]);
    if(cnt>0) printf("\n");

    return;
}

int main()
{
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++) solve();
    return 0;
}